package 剑指Offer.medium;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class 复杂链表的复制 {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    class Solution {
        public Node copyRandomList(Node head) {
            if (head == null) return null;
            Map<Node, Node> map = new HashMap<>();
            Node cur = head;
            //复制新结点，形成映射
            while (cur != null) {
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }
            //复制关系
            cur = head;
            while (cur != null) {
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
        }
    }

 /*   class Solution {
        public Node copyRandomList(Node head) {
            Deque<Node> deque = new LinkedList<>();
            Node root = new Node(-1);
            if (head != null) {
                root.val = head.val;
                root.next = head.next;
                root.random = head.random;
                deque.add(root);
            }
            while (!deque.isEmpty()) {
                int size = deque.size();
                for (int i = 0; i < size; i++) {
                    Node poll = deque.poll();
                    Node next = poll.next;
                    Node random = poll.random;
                    //创建新结点
                    Node node = new Node(poll.val);
                    node.next = next;
                    node.random = random;

                    if (next != null) deque.add(next);
                    if (random != null) deque.add(random);
                }
            }
            return root;
        }
    }*/

    /*Node nodeNext = new Node(next.val);
                    nodeNext.next = next.next;
                    nodeNext.random = next.random;
                    Node nodeRandom = new Node(random.val);
                    nodeRandom.next = random.next;
                    nodeRandom.random = random.random;

                    node.next = nodeNext;
                    node.random = nodeRandom;*/
}
